#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int inf = 0x3f3f3f3f;
const int N = 1010;

int n, W, a[N], p[N], q[N], top, s1[N], s2[N], ndn;

namespace F { // max_flow_with_cost
	const int N = 5e4 + 10;
	const int M = 1e6 + 10;
    const int inf = 0x3f3f3f3f;
    int h[N], now[N], cnt = 1, S, T;
    bool vis[N];
    ll maxflow, cost, dis[N];
    struct edge { int v, w, c, nxt; } e[M << 1];
    inline void tlink(int x, int y, int w, int c) { e[++cnt] = (edge) { y, w, c, h[x] }; h[x] = cnt; }
    inline void link(int x, int y, int w, int c) { tlink(x, y, w, c); tlink(y, x, 0, -c); }
    inline void setst(int s, int t) { S = s; T = t; }
    bool bfs() {
		queue < int > q; q.push(S); memset(dis, 0x3f, sizeof dis); memset(vis, 0, sizeof vis); dis[S] = 0; now[S] = h[S]; vis[S] = 1;
		while(!q.empty()) {
			int x = q.front(); q.pop();
			for(int i = h[x], y; i; i = e[i].nxt)
				if(e[i].w && dis[y = e[i].v] > dis[x] + e[i].c) {
					dis[y] = dis[x] + e[i].c; now[y] = h[y];
					if(!vis[y]) vis[y] = 1, q.push(y);
				}
			vis[x] = 0;
		} return dis[T] < inf;
    }
    int dinic(int x,int flow,ll c) {
		if(x == T) return maxflow += flow, cost += c * flow, flow;
		int res = flow; vis[x] = 1;
		for(int i = now[x], y; i && res; i = e[i].nxt) {
			now[x] = i;
			if(e[i].w && dis[y = e[i].v] == dis[x] + e[i].c && !vis[y]) {
				int k = dinic(y, min(res,e[i].w), c + e[i].c); 
				e[i].w -= k; e[i ^ 1].w += k; res -= k;
			}
		} vis[x] = 0;
		return flow - res;
    }
    void runit() { while(bfs()) dinic(S, inf, 0); }
}

void solve(int l, int r) {
	if(l == r) return; int mid = l + r >> 1;
	solve(l, mid); solve(mid + 1, r);
	rep(i, l, mid) s1[i] = ++ndn, ((i > l) && (F :: link(s1[i], s1[i - 1], inf, 0), 1)), F :: link(s1[i], p[i] + n, 1, -a[p[i]]);
	per(i, mid, l) s2[i] = ++ndn, ((i < mid) && (F :: link(s2[i], s2[i + 1], inf, 0), 1)), F :: link(s2[i], p[i] + n, 1, a[p[i]]);
	int pos = l;
	rep(i, mid + 1, r) {
		int x = p[i]; while(pos <= mid && a[p[pos]] <= a[x]) pos++;
		if(pos > l) F :: link(x, s1[pos - 1], 1, a[x]);
		if(pos <= mid) F :: link(x, s2[pos], 1, -a[x]);
	}
	inplace_merge(p + l, p + mid + 1, p + r + 1, [](auto x, auto y) { return a[x] < a[y]; });
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, W = in; rep(i, 1, n) a[i] = in;
	rep(i, 1, n) p[i] = i;
	ndn = 2 * n + 1; F :: setst(0, ndn);
	rep(i, 1, n) F :: link(0, i, 1, 0), F :: link(i, ndn, 1, W), F :: link(i + n, ndn, 1, 0);
	solve(1, n); F :: runit(); printf("%lld\n", F :: cost);
	return 0;
}
